"""
合并排序
O(logN)
"""


# 合并数组，小的在前 大的在后
def Merge(a, left, mid, right):
    if left >= right:
        return
    b = []
    i = left
    j = mid + 1
    while i <= mid and j <= right:
        if a[i] < a[j]:
            b.append(a[i])
            i = i + 1
        else:
            b.append(a[j])
            j = j + 1

    while i <= mid:
        b.append(a[i])
        i = i + 1
    while j <= right:
        b.append(a[j])
        j = j + 1
    # print("合并后b :", b)
    for x in range(len(b)):
        a[left + x] = b[x]


# 递归实现
def MergeSort(a, l, r):
    # print(a)
    if l < r:
        mid = int((l + r) / 2)
        MergeSort(a, l, mid)
        MergeSort(a, mid + 1, r)
        Merge(a, l, mid, r)
    # return


# a = [1, 9, 9, 6, 44, 3, 2, 77, 4, 87, 34, 56, 456]
# MergeSort(a, 0, len(a) - 1)
# print("第一次导入时会运行本语句\n最终合并结果", a)
